This invention relates to a network management system for satisfying a request for a connection path having a specified capacity between two specified terminations and to a method of operating such a system. It is particularly concerned with a network management system for a synchronous digital hierarchy (SDH) network, but has application in other types of networks as well.
A typical digital telecommunications network for transmission of voice or data operates at a sampling rate of 8000 samples/sec; (1 per 125 microseconds). Each sample is coded as an 8-bit byte, resulting in a 64 kbit/sec bit rate. This is typically multiplexed over the network in a 32-channel frame (including one channel each for synchronisation and signalling), resulting in a transmission rate of 64xc3x9732=2,048 kbits/sec, known as a 2 Mbit system. Further multiplexing can take place by multiplexing four lower level channels into one higher level channel to produce a secondary bit rate of 8 Mbits/s, and this process can be repeated to produce tertiary (34 Mbit/s), and quaternary (140 Mbit/s) bit rates. These are not exact quadruples because of the need for an additional signalling overhead to be included.
The bit rates quoted above are those used in Europe. In other regions such as the USA and Japan, although the fundamental bit rate is the same 64 kbit/s, the samples are initially multiplexed in a 24 channel frame (rather than 32) to produce a primary bit rate of 1.544 Mbit/s, a secondary bit rate of 6.312 Mbit/s, a tertiary bit rate of 32 Mbit/s (Japan) or 45 Mbit/s (USA), and a quaternary bit rate of 98 Mbit/s (Japan) or 140 Mbit/s (USA). A network which operates at these bit rates and which has multiplexers/demultiplexers for converting from one rate to another is known as a xe2x80x9cplesiochronousxe2x80x94i.e. nearly synchronousxe2x80x94digital hierarchyxe2x80x9d: (PDH) network. A disadvantage of such a network is that at any point in the network at which different channels need to be separately routed, the signals have to be demultiplexed step-by-step back to a 64 kbit/s signal in order that the individual channels can be identified. This is necessary even if the channels are then to be immediately re-multiplexed up to one of the higher bit-rates for onward transmission.
The Synchronous Digital Hierarchy (SDH) is a standard which not only allows transmission at all the above bit rates to be carried, but allows individual signals to be added or extracted without demultiplexing other signals multiplexed with it. In an SDH link operating at 155 Mbit/s, the signal is divided into frames known as STM-1 frames. Each frame comprises 2430 bytes, 2349 of which are available as payload, the rest being for signalling and synchronisation. This corresponds to a payload bit rate of 150 Mbit/s.
Each 150 Mbit/s STM-1 frame consists of one or more xe2x80x98virtual containersxe2x80x99. There are five types:
A VC11 has a capacity of 1.7 Mbit/s and can carry one 1.5 Mbit/s primary channel according to the US or Japanese 24xc3x9764 kbit/s standard.
A VC12 has a capacity of 2.3 Mbit/s and can carry one 2 Mbit/s primary channel according to the European 30xc3x9764 kbit/s standard.
A VC2 has a capacity of 6.8 Mbit/s and can carry one 6.3 Mbit/s channel (the US/Japanese secondary level), or four VC11""s or three VC12""s.
A VC3 has a capacity of 50 Mbit/s, allowing it to support any of the tertiary level PDH bit rates: 32 Mbit/s (Japan), 34 Mbit/s (Europe), or 44 Mbit/s (USA). It may instead carry seven VC2""s, twenty-one VC12""s or twenty-eight VC11""s.
A VC4 has a capacity of 150 Mbit/s, allowing it to support the quaternary PDH bit rate of 140 Mbit/s (or 98 Mbit/s in Japan), or three VC3""s, twenty-one VC2""s, sixty-three VC12""s or eighty-four VC11""s.
Mixtures of virtual containers may also be carried: for example an STM-1 frame might consist of one VC3, nine VC2""s, nine VC12""s and eight VC11""s. The VC3 may itself contain VC11""s, VC12""s or VC2""s (or a mixture), and the VC2""s may themselves contain VC11""s or VC12""s.
SDH links can operate at higher bit rates. For example, in an SDH link operating at 622 Mbit/s, the signal is divided into frames known as STM-4 frames, each of which has a payload four times greater than an STM-1 frame.
SDH networks have advantages over PDH networks. In particular, the STM-1 frame includes data regarding each individual virtual container within it, which allows the channel represented by that container to be demultiplexed and routed separately at any network node without the need to dismantle the whole frame. In contrast, in a PDH network the individual channels are not identifiable and extractable without undoing each multiplexing stage in turn down to the required level, and then remultiplexing the channels not extracted for further transmission.
In an SDH network traffic capacity can be booked in advance, on request of the user. It is then necessary to meet this request by allocating a path through the network having the required capacity. The customer may have specific requirements, for example two or more independent paths may be required, sharing no individual links or nodes, to ensure that an individual failure does not result in loss of the entire booked capacity. The path allocated to the customer may then be used in any way he requires, eg to route individual calls. It should be noted that capacity management involves different requirements to the handling of individual call traffic. In particular, capacity management has to consider future requirements for capacity, and not just the real-time requirements that a call-traffic management system has to deal with. Ideally a capacity management system should also be able to provide capacity immediately, perhaps as a premium (xe2x80x9cJust In Timexe2x80x9d) service. Moreover, in a call traffic management system, it is normally optimal to try to spread call traffic over as many different routes as possible, to minimise interference and ensure minimum disruption if one route should fail. In capacity management, the optimum is to aggregate low capacity routes where possible, to fully load each link that is used, thereby keeping other links free. The free links can then be used if a subsequent requirement for a high-capacity link is received, without having to first re-allocate low capacity links.
The availability of connections between nodes within the network depends on a number of factors which are constantly changing. For example, equipment is taken out of service for maintenance, and re-instated afterward. This may be on a planned or emergency basis. Moreover, as capacity is allocated to one user it becomes unavailable for use by others.
In order to control the routing of transmissions through an SDH network, it is therefore necessary to allocate capacity over the network between the source and destination. Various criteria need to be addressed, such as the capacity required, the time the capacity is needed, the length of time needed, the need for robustness (addressed for example by routing part of the capacity over one path and part over another, a practice known as xe2x80x98diversityxe2x80x99, such that a connection is maintained, albeit at lower capacity, even should one path fail), and any variations in availability of capacity e.g. because of planned maintenance, or other users of the system.
In order to establish the routing to be taken by a transmission, the various connections to be used in the network need to be allocated and reserved. The capacity may be required immediately, or the capacity may be reserved in advance against an expected requirement.
It is possible to envisage a path-finding system in which a path is sought from first principles every time a new request for capacity is made, by analysing the network connectivity and its committed capacity, and calculating a path through it. For a complex network, such an exhaustive analysis would involve a large amount of processor power, and to explore all the possible connections would be very slow. Much of the processing could be redundant, since repeated requests for connection between the same two points would usually be satisfied by the same routing.
An alternative approach is to maintain a listing of all possible paths between any given starting point and any given end point. On request for capacity between such points, the optimum path having sufficient capacity (allowing for any capacity already committed or out of service), can be selected. This method is impracticable for a network of any size, because it requires a very large memory size. There are an unmanageably high number of possible paths through a complex network, and although most of these paths are sub-optimal, they may be needed if the best path stored is unavailable for any reason, such as link failure or capacity already committed. This method also requires constant updating as the network evolves, and requires routings for which capacity is already committed to be expressly considered and rejected.
According to the invention there is provided a method of operating a network management system for a telecommunications network in order to satisfy a request for a connection path having a specified capacity between two specified terminations of the network, the network comprising a plurality of connections between network nodes, each connection having a predetermined capacity, the method comprising the steps of searching a store of routings and available capacities to identify a connection path to satisfy the request; determining whether a connection path with adequate capacity is present in the store; if no such path is present in the store, testing a model of the network to identify at least one suitable connection path between the requested terminations, and adding any suitable connection paths so identified to the store, and upon identifying a connection path having the requested capacity between the requested terminations, allocating the identified connections so as to satisfy the request.
It will be noted that this method does not necessarily identify the optimum solution, as the search is not exhaustive. An exhaustive search would take a very large amount of computer time, and the result would only remain optimal until the next request for capacity is made, when the entire allocation scheme would have to be rebuilt. Instead, the method of the invention identifies a good (but not necessarily perfect) solution in a reasonable time, thereby trading perfection for speed.
In a preferred arrangement the store of routings and available capacities is updated in response to connection paths becoming available or unavailable. In this way duplication of processing is avoided, whilst the memory need only store routings which are likely to be required.
By maintaining a store of paths which have been determined, but allowing new paths to be added, the method reduces the total processing time required, whilst still allowing changes in availability to be accommodated.
In a further preferred arrangement capacity is allocated in advance, in response to a request, but the allocation of individual paths to connections is made at the time for which the path is required. In this way the utilisation of capacity can be optimised, without jeopardising the traffic which has already reserved capacity.
The path finding process may comprise the following steps:
identifying a start point and a target point;
identifying, from the nodes in the network directly connected to the start point, that node which is most appropriate for approaching the target point;
establishing the connection between the start point and the node so identified as the first link in the connection path;
repeating the process using the identified node as the new start point, until a connection is made with the target point.
Preferably, the identification of the most appropriate node takes into account the distance of the target, and the structure of the network. In a typical hierarchical structure, weighting factors can be applied to different nodes to preferentially select a node at a level in the hierarchy most appropriate for the distance to the target.
This approach does not rigorously explore all possible paths, but at each step analyses the most likely possibility. Unless the network has any very unusual features this will produce an answer close to optimum. In a typical hierarchical network comprising a plurality of levels each of which comprises a ring, the majority of nodes only have two connections, thereby simplifying the analysis process.
Whilst not rigorous, this process will find the optimum routing, or one very close to optimum, in the majority of cases provided the network is well structured. Safeguards can be included to ensure that the path selected is not unreasonable. In particular when a node is established as forming part of a connection path, said node can be excluded from consideration in any further links in the path. If all nodes connected to the current start point are excluded from consideration, (as may be the case if they already form part of the path, are currently fully committed or are out of service) the link connected to the current start node may be deleted and the process repeated from the previous start node. Preferably, at each stage any node connected either to the current start node or to any other nodes already forming part of the current connection path (other than any excluded node), can be considered as a candidate for the next link, and if a node connected to an existing node other than the current start node is selected, the links between the existing node and the current start node are deleted from the connection path and the link between the existing node and the new node is added to the connection path.
The rules may also limit the number of transitions between hierarchical levels. In particular, the rules may require that nodes at the same level may only be connected to each other by a path using nodes at the same or a higher level.
The method may be carried out starting from both end points, generating two half paths, the target point of each half path being redefined at each interaction as the current start point of the other half path. In this case the rule referred to above limiting the number of level transitions can be defined more simply as requiring that each link of each half path, starting at its respective end point, can only link to a node at the same or a higher level as the current start point.
It should be recognised that the term xe2x80x98half-pathxe2x80x99 is used in this description, to mean a part of a path built up from one end. The two half-paths making up the complete path are not necessarily the same length.
In a preferred arrangement, the method may comprise the further step of monitoring the available capacity present in the store, and providing an alert if the available capacity falls below a predetermined minimum. The capacity may be monitored by determining whether the step of testing the model fails to identify a suitable connection path. This allows the system administrator to be alerted to imminent capacity shortages before they become critical.